By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 17, Issue 6, pp. 1063-1282

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs

Thomas Lengauer and Egon Wanke

pp. 1063-1080

BibTeX  Abstract Full Text:  PDF

A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots

Michael Ben-Or, Ephraim Feig, Dexter Kozen, and Prasoon Tiwari

pp. 1081-1092

BibTeX  Abstract Full Text:  PDF

A Lower Bound on the Complexity of the Union-Split-Find Problem

Kurt Mehlhorn, Stefan Näher, and Helmut Alt

pp. 1093-1102

BibTeX  Abstract Full Text:  PDF

A Short-Term Neural Network Memory

Robert J. T. Morris and Wing Shing Wong

pp. 1103-1118

BibTeX  Abstract Full Text:  PDF

Transitive Orientations of Graphs

Béla Bollobás and Graham Brightwell

pp. 1119-1133

BibTeX  Abstract Full Text:  PDF

Readies and Failures in the Algebra of Communicating Processes

J. A. Bergstra, J. W. Klop, and E.-R. Olderog

pp. 1134-1177

BibTeX  Abstract Full Text:  PDF

The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms

N. Alon and Y. Azar

pp. 1178-1192

BibTeX  Abstract Full Text:  PDF

P-Printable Sets

Eric W. Allender and Roy S. Rubinstein

pp. 1193-1202

BibTeX  Abstract Full Text:  PDF

Search in an Ordered Array Having Variable Probe Cost

William J. Knight

pp. 1203-1214

BibTeX  Abstract Full Text:  PDF

The Decomposition of a Rectangle into Rectangles of Minimal Perimeter

T. Y. Kong, David M. Mount, and A. W. Roscoe

pp. 1215-1231

BibTeX  Abstract Full Text:  PDF

The Boolean Hierarchy I: Structural Properties

Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus Wagner, and Gerd Wechsung

pp. 1232-1252

BibTeX  Abstract Full Text:  PDF

On Finding Lowest Common Ancestors: Simplification and Parallelization

Baruch Schieber and Uzi Vishkin

pp. 1253-1262

BibTeX  Abstract Full Text:  PDF

The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

Jim Kadin

pp. 1263-1282

BibTeX  Abstract Full Text:  PDF